package zty.structures.queue;

import java.util.Scanner;

/**
 * 队列实现，存储数据使用数组
 * @author tyzhang
 * @Date: 2021/1/11 10:05
 */
public class QueueDemo {
    public static void main(String[] args) {
//        int [] array = new int[]{1,6,4,3,7};
//        QueueArray queue = new QueueArray(5);
//        queue.addDataArray(array);
//        queue.addData(5);
//        int head1 = queue.shouHead();
//        int data1 = queue.getData();
//        System.out.printf("头元素head为：%d，取出的头元素data为：%d，剩余队列为：\n",head1,data1);
//        queue.showQueue();
//        System.out.println();
//        int head2 = queue.shouHead();
//        int data2 = queue.getData();
//        System.out.printf("头元素head为：%d，取出的头元素data为：%d,剩余队列为：\n",head2,data2);
//        queue.showQueue();

        System.out.println("测试数组模拟环形队列的案例~~~");
        // 创建一个环形队列
        QueueArray queue = new QueueArray(4);
        // 接收用户输入
        char key = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        // 输出一个菜单
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            // 接收一个字符
            key = scanner.next().charAt(0);
            switch (key) {
                case 's':
                    queue.showQueue();
                    System.out.println();
                    break;
                case 'a':
                    System.out.println("输入一个数");
                    int value = scanner.nextInt();
                    queue.addData(value);
                    break;
                case 'g':
                    try {
                        int res = queue.getData();
                        System.out.printf("取出的数据是%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int res = queue.shouHead();
                        System.out.printf("队列头的数据是%d\n", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出~~");
    }
}

class QueueArray{
    /** 队列最大长度 */
    private final int maxSize;
    /** 队列头 */
    private int front;
    /** 队列尾 */
    private int rear;
    /** 队列中存储数据 */
    private int[] arr;

    /**
     * 初始化队列
     * 环形队列，front与rear 初始化为0，指向队列第一个元素
     * 判断环形队列满的方法： （rear+1） % maxsize == front
     *                 +1 因为队列预留一个空间，防止溢出
     * 判断环形队列元素个数的方法：   （rear + maxsize - front）% maxsize
     *                  +maxsize 防止环形队列出现rear - front 出现负数
     * @param maxSize 队列最大长度
     */
    public QueueArray(int maxSize){
        this.maxSize = maxSize;
        arr = new int[maxSize];
        front = 0;
        rear = 0;
    }

    /** 判断队列是否满 */
    public boolean isFull(){
        if ((rear + 1) % maxSize == front){
            System.out.println("队列已满~~~~");
            return true;
        }
        return false;
    }

    /** 判断队列是否空 */
    public boolean isEmpty() {
        return front == rear;
    }

    /** 向队列添加数据 */
    public void addData(int data){
        if (isFull()){
            System.out.println("队列已满~~~");
            return;
        }
        arr[rear] = data;
        // 环形队列取模防止rear溢出
        rear = (rear + 1) % maxSize;
    }

    /**
     * 向队列添加一个数组
     * @param data 要添加的数组
     */
    public void addDataArray(int[] data){
        // 为while命名为outer：（for也可以使用）
        outer: while (!isFull()){
            for (int d : data) {
                rear++;
                arr[rear] = d;
                if (rear == maxSize - 1){
                    showQueue();
                    System.out.println();
                    System.out.println("队列已经添加满了~~~");
                    // 退出outer(while)循环
                    break outer;
                }
            }
        }
    }

    /** 向队列取数据 */
    public int getData(){
        if (isEmpty()){
            throw new RuntimeException("队列为空~~~~~");
        }
        int data = arr[front];
        front = (front + 1) % maxSize;
        return data;
    }

    /** 展示队列 */
    public void showQueue(){
        if (!isEmpty()){
            for (int i = front; i < front + size(); i ++){
                // front % maxsize 防止溢出
                System.out.printf("arr[%d] = %d\n",i % maxSize,arr[i % maxSize]);
            }
        }else {
            System.out.println("队列无数据~~~");
        }
    }

    /** 计算队列有效数据个数 */
    public int size(){
        /**
         * maxsize = 4
         * front = 3
         * rear = 1
         * queue.size = 2
         */
        return (rear + maxSize - front) % maxSize;
    }

    /** 查看队列头数据 */
    public int shouHead(){
        if (!isEmpty()){
            return arr[front];
        }else {
            throw new RuntimeException("空队列");
        }
    }
}